package com.github.anhTom2000.algorithm.sort;

import java.util.Arrays;

/**
 * @author yangguang
 * @date 2020/4/20
 * @since
 * <p>
 *      冒泡排序
 * </p>
 */
public class BubbleSort
{
    public static void main(String[] args)
    {
        int[] arr = {3,5,0,-9,8,30,25,8,10,32};

        /***
         *
         * 第一次：
         *  第一趟：3,5,0,-9,8,30,25
         *  第二趟：3,0,5,-9,8,30,25
         *  第三趟：3,0,-9,5,8,30,25
         *  第四趟：3,0,-9,5,8,30,25
         *  第五趟：3,0,-9,5,8,30,25
         *  第六趟：3,0,-9,5,8,25,30        30最大确定了下来
         *
         * 第二次：
         *  第一趟：0,3,-9,5,8,25,30
         *  第二趟：0,-9,3,5,8,25,30
         *  第三趟：0,-9,3,5,8,25,30
         *  第四趟：0,-9,3,5,8,25,30
         *  第五趟：0,-9,3,5,8,25,30       25确定了下来
         *
         * 第三次：
         *  第一趟：-9,0,3,5,8,25,30
         *  第二趟：-9,0,3,5,8,25,30
         *  第三趟：-9,0,3,5,8,25,30
         *  第四趟：-9,0,3,5,8,25,30      8确定了下来
         *
         * 第四次：
         *  第一趟： -9,0,3,5,8,25,30
         *  第二趟： -9,0,3,5,8,25,30
         *  第三趟： -9,0,3,5,8,25,30    5确定了下来
         *
         * 第五次：
         *  第一趟： -9,0,3,5,8,25,30
         *  第二趟： -9,0,3,5,8,25,30   3确定了下来
         *
         * 第六次：
         *   第一趟：-9,0,3,5,8,25,30   0确定了下来
         *
         *
         *
         *   总结: 一共有7个元素，共比较了 6 次， 即 总共需要比较 arr.length - 1 次
         *
         *
         *       但是有没有优化第空间，是否每个数组都需要比较 arr.length - 1 次，其实我们发现，第三次比较的时候，整个数组就已然是有序的了。
         *       所以从这点就可以看出来是有优化空间的。
         *
         *
         */

        int temp;
        boolean flag = true;
        for (int i = 0 ; i < arr.length - 1; ++i)
        {
            for(int j = 0 ; j < arr.length - 1; ++j)
            {
                if((temp = arr[j]) > arr[j + 1])
                {
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = false;
                }
            }
            if(flag)
            {
                break;
            }
        }
        System.out.println("冒泡排序后的数组: ");
        System.out.println(Arrays.toString(arr));
    }
}
